//
// Created by Martin on 2022/5/10.
//

#ifdef __GUNC__
#include <bits/stdc++.h>

#else
#include <vector>
#include <iostream>
#include <random>

#endif // __GUNC__


using namespace std;

//------------------------------------------------------
// AVL Tree 二叉平衡搜索树
// TOJ 3374

typedef struct AVLNode {
	int data;
	int height;
	struct AVLNode* lchild;
	struct AVLNode* rchild;
}*AVLTree;

int Height(AVLTree T) { // 计算高度
	if (!T) return 0;
	return T->height;
}

void updateHeight(AVLTree& T) { // 更新高度, 根据儿子节点高度来更新当前节点高度
	T->height = max(Height(T->lchild), Height(T->rchild)) + 1;
}

// 以T为最小不平衡子树的不平衡点, 进行LL旋转
AVLTree LL_Rotation(AVLTree& T) {
	AVLTree temp = T->lchild;
	T->lchild = temp->rchild;
	temp->rchild = T;
	updateHeight(T); // 更新高度
	updateHeight(temp);
	return temp;
}

// 以T为最小不平衡子树的不平衡点, 进行RR旋转
AVLTree RR_Rotation(AVLTree& T) {
	AVLTree temp = T->rchild;
	T->rchild = temp->lchild;
	temp->lchild = T;
	updateHeight(T); // 更新高度
	updateHeight(temp);
	return temp;
}

// 以T为最小不平衡子树的不平衡点, 进行LR旋转
AVLTree LR_Rotation(AVLTree& T) {
	T->lchild = RR_Rotation(T->lchild);
	return LL_Rotation(T);
}

// 以T为最小不平衡子树的不平衡点, 进行RL旋转
AVLTree RL_Rotation(AVLTree& T) {
	T->rchild = LL_Rotation(T->rchild);
	return RR_Rotation(T);
}

AVLTree Insert(AVLTree& T, int x) {
	if (!T) { // 如果为空则创建新节点
		T = new AVLNode;
		T->lchild = T->rchild = NULL;
		T->data = x;
		T->height = 1;
		return T;
	}
	if (T->data == x) return T; // 查找成功, 什么也不做, 查找失败时才插入x
	if (x < T->data) { // 插入左子树
		T->lchild = Insert(T->lchild, x);
		if (Height(T->lchild) - Height(T->rchild) == 2) { // 如果不平衡, 平衡因子: 2
			if (x < T->lchild->data) { // 判断是LL, 还是LR
				T = LL_Rotation(T);
			}
			else {
				T = LR_Rotation(T);
			}
		}
	}
	else { // 插入右子树
		T->rchild = Insert(T->rchild, x);
		if (Height(T->rchild) - Height(T->lchild) == 2) {  // 如果不平衡, 平衡因子: -2
			if (x > T->rchild->data) { // 判断是RR, 还是RL
				T = RR_Rotation(T);
			}
			else {
				T = RL_Rotation(T);
			}
		}
	}
	updateHeight(T);
	return T;
}

// 删除节点后, 需要判断是否仍平衡, 如果不平衡, 则需要调整
AVLTree adjust(AVLTree& T) {
	if (!T) return NULL;
	if (Height(T->lchild) - Height(T->rchild) == 2) { // 沿着高度大的那条路径判断
		if (Height(T->lchild->lchild) >= Height(T->lchild->rchild)) { // LL
			T = LL_Rotation(T);
		}
		else { // LR
			T = LR_Rotation(T);
		}
	}
	if (Height(T->rchild) - Height(T->lchild) == 2) {
		if (Height(T->rchild->rchild) >= Height(T->rchild->lchild)) { // RR
			T = RR_Rotation(T);
		}
		else { // RL
			T = RL_Rotation(T);
		}
	}
	updateHeight(T); // 结构调整以后, 需要重新计算高度
	return T;
}

// 删除所有值为x的节点
AVLTree Delete(AVLTree& T, int x) {
	if (!T) return NULL;
	if (T->data == x) { // 如果找到待删除节点
		if (!T->rchild) { // 如果该节点的右孩子为NULL, 那么直接将其删除, 并挂接上左孩子为这个节点
			AVLTree temp = T;
			T = T->lchild;
			delete temp;
		}
		else { // 否则, 将右子树的最左孩子作为这个节点, 并且递归删除这个节点的值
			AVLTree temp;
			temp = T->rchild;
			while (temp->lchild) {
				temp = temp->lchild;
			}
			T->data = temp->data;
			T->rchild = Delete(T->rchild, T->data); // 在右子树中递归删除x
			updateHeight(T);
		}
		return T;
	}

	if (T->data > x) { // 调整删除节点后可能涉及的节点
		T->lchild = Delete(T->lchild, x); // 在左子树中递归删除x
	}
	if (T->data < x) {
		T->rchild = Delete(T->rchild, x); // 在右子树中递归删除x
	}
	updateHeight(T);
	T = adjust(T);
	return T;
}

AVLTree CreateAVL(AVLTree& T) {
	int n, x;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> x;
		T = Insert(T, x);
	}
	return T;
}

void ClearAVL(AVLTree& T) {

}

//------------------------------------------------------
// 测试AVLTree

void print_vector(vector<int>& vec) {
	cout << "{";
	for (int i = 0; i < vec.size(); ++i) {
		cout << vec[i];
		if (i < vec.size() - 1) {
			cout << ", ";
		}
	}
	cout << "}" << endl;
}

int main()
{
	int n, val;
	int test_cast_num = 0;

	{ // 固定测试用例 from TOJ 3374
		AVLTree root = NULL;
		cout << "test case " << ++test_cast_num << ": " << endl;
		vector<int> vec = { 88, 70, 61, 96, 120 };
		for (int i = 0; i < vec.size(); ++i) {
			Insert(root, vec[i]);
		}
		cout << "AVL Tree root = " << root->data << endl;
	}

	{ // 随机生成测试用例
		AVLTree root = NULL;
		cout << "test case " << ++test_cast_num << ": " << endl;
		default_random_engine e;
		uniform_int_distribution<int> u(1, 200);
		vector<int> vec;
		n = 50;
		for (int i = 0; i < n; ++i) {
			int d = u(e);
			vec.push_back(d);
			Insert(root, d);
		}

		cout << "origin vector = ";
		print_vector(vec);

		cout << "AVL Tree root = " << root->data << endl;
	}

#if 0 // 手动输入测试用例
	{
		AVLTree root = NULL;
		cout << "test case " << ++test_cast_num << ": " << endl;
		cin >> n;
		for (int i = 0; i < n; ++i) {
			cin >> val;
			Insert(root, val);
		}
		cout << root->data << endl;
}
#endif

	return 0;
}
